home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_400 / 425_01 / lzpipe / compress.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-02-24  |  12.4 KB  |  444 lines
  1. /* Compress - data compression program */
  2. /* machine variants which require cc -Dmachine:    pdp11, z8000, pcxt */
  3.  
  4. /* The following code is derived from regular 'compress' program, */
  5. /* revision 4.0 85/07/30 by Joe Orost (decvax!vax135!petsd!joe)   */
  6.  
  7. /*
  8.  * Algorithm from "A Technique for High Performance Data Compression",
  9.  * Terry A. Welch, IEEE Computer Vol 17, No 6 (June 1984), pp 8-19.
  10.  *
  11.  * Algorithm:
  12.  *    Modified Lempel-Ziv method (LZW).  Basically finds common
  13.  * substrings and replaces them with a variable size code.  This is
  14.  * deterministic, and can be done on the fly.  Thus, the decompression
  15.  * procedure needs no input table, but tracks the way the table was built.
  16.  */
  17. #include <stdio.h>
  18. #include "modern.h"
  19. #include "lzpipe.h"
  20. #include "lzwbits.h"
  21.  
  22. #ifndef USG
  23. #    ifdef i386
  24. #        define SYS_V
  25. #    endif
  26. #    ifdef M_XENIX
  27. #        define SYS_V
  28. #    endif
  29. #endif
  30.  
  31. #ifdef SYS_V
  32. #    include <memory.h>
  33. #    ifndef MEMSET
  34. #        define MEMSET
  35. #    endif
  36. #endif
  37.  
  38. #ifdef MSC_VER
  39. #    include <memory.h>
  40. #    ifndef MEMSET
  41. #        define MEMSET
  42. #    endif
  43. #endif
  44.  
  45. #ifdef __TURBOC__
  46. #    include <mem.h>
  47. #    ifndef MEMSET
  48. #        define MEMSET
  49. #    endif
  50. #endif
  51. #ifdef MEMSET
  52. #    if ~0 != -1
  53. #        undef MEMSET
  54. #    endif
  55. #endif
  56. #ifdef MEMSET
  57. #    define M1 (~0)
  58. #else
  59. #    define M1 (-1)
  60. #endif
  61.  
  62. #ifdef XENIX_16
  63. static code_int c_hashsize;
  64. # define c_HSIZE c_hashsize
  65. #else
  66. # define c_HSIZE _HSIZE
  67. #endif
  68.  
  69. #ifdef MODERN
  70. #    include <stdlib.h>
  71. #else
  72.     char *malloc();
  73.     void free();
  74. #endif
  75.  
  76. static int c_n_bits;    /* number of bits/code */
  77. static int c_maxbits = BITS;    /* user settable max # bits/code */
  78. static code_int c_maxcode;    /* maximum code, given n_bits */
  79. /* should NEVER generate this code */
  80. static code_int c_maxmaxcode = (code_int)1 << BITS;
  81.  
  82. #define word_type unsigned short
  83. #define WNIL (word_type)0
  84. #define CNIL (count_int)0
  85.  
  86. #ifdef XENIX_16
  87.   static count_int *htab[MAXPAGES];
  88.   static word_type *codetab[MAXPAGES] = {WNIL};
  89.  
  90. # define htabof(i)       (htab[(int)((i) >> PAGEXP)][(int)(i) & PAGEMASK])
  91. # define codetabof(i)    (codetab[(int)((i) >> PAGEXP)][(int)(i) & PAGEMASK])
  92. #else
  93.   static count_int *htab;
  94.   static word_type *codetab = WNIL;
  95. # define htabof(i)       htab[i]
  96. # define codetabof(i)    codetab[i]
  97. #endif
  98. static code_int hsize = _HSIZE; /* for dynamic table sizing */
  99.  
  100. static code_int c_free_ent = 0; /* first unused entry */
  101.  
  102. /* block compression parameters -- after all codes are */
  103. /* used up, and compression rate changes, start over.  */
  104. static int c_block_compress = BLOCK_MASK;
  105. static int c_clear_flg = 0;
  106. static long int ratio = 0;
  107. static count_int c_checkpoint = CHECK_GAP;
  108.  
  109. static void cl_hash __ARGS__((count_int));
  110.  
  111. static void cl_hash(clsize) /* reset code table */
  112. register count_int clsize;
  113. {
  114. #ifdef XENIX_16
  115.    register j, l;
  116. # ifndef MEMSET
  117.    register i;
  118. # endif
  119.  
  120.    for (j=0; j<MAXPAGES && clsize>=0; j++, clsize-=PAGESIZE) {
  121.        l = clsize<PAGESIZE ? (int)clsize : PAGESIZE;
  122. # ifdef MEMSET
  123.        (void)memset((char*)htab[j], M1, l*sizeof(**htab));
  124. # else
  125.        for (i=0; i<l; i++) htab[j][i] = M1;
  126. # endif
  127.    }
  128. #else
  129. # ifdef MEMSET
  130.    (void)memset(htab, M1, clsize*sizeof(*htab));
  131. # else
  132.    register count_int i; for (i=0; i<clsize; i++) htab[i] = (count_int)M1;
  133. # endif
  134. #endif
  135. }
  136.  
  137. static int  offset;
  138. static long in_count=1;    /* length of input */
  139. static long bytes_out;    /* length of compressed output */
  140.  
  141. #ifdef LZFILE
  142.     static FILE *lzw_out_port = NULL;
  143. #    define putbyte(b) putc((b), lzw_out_port)
  144. #else
  145.     static int (*lzw_out_port)__ARGS__((int)) = NULL;
  146. #    define putbyte(b) (*lzw_out_port)(b)
  147. #endif
  148.  
  149. static int putpiece __ARGS__((char *, int));
  150.  
  151. static int putpiece(p, n)
  152. register char *p; register n;
  153. {
  154.    offset = 0;
  155.    bytes_out += n;
  156.    while (n-- > 0) {
  157.       if (putbyte(*p++) == EOF) return -1;
  158.    }
  159.    return 0;
  160. }
  161.  
  162. /* Output the given code.
  163.  * Inputs:
  164.  *    code:    A n_bits-bit integer.  If == -1, then EOF.  This assumes
  165.  *        that n_bits =< (long)wordsize - 1.
  166.  * Outputs:
  167.  *    Outputs code to the file.
  168.  * Assumptions:
  169.  *    Chars are 8 bits long.
  170.  * Algorithm:
  171.  *    Maintain a BITS character long buffer (so that 8 codes will
  172.  * fit in it exactly).    Use the VAX insv instruction to insert each
  173.  * code in turn.  When the buffer fills up empty it and start over.
  174.  */
  175.  
  176. static char outbuf[BITS];
  177.  
  178. static int output __ARGS__((word_type));
  179.  
  180. static int output(code)
  181. word_type code;
  182. {
  183. #ifndef vax
  184.    static char_type rmask[] = {0x00,0x01,0x03,0x07,0x0f,0x1f,0x3f,0x7f};
  185. #endif
  186.    /* On the VAX, it is important to have the register declarations */
  187.    /* in exactly the order given, or the asm will break.            */
  188.    register int r_off = offset, bits = c_n_bits;
  189.    register char *bp = outbuf;
  190.  
  191. #ifdef vax
  192.    /* VAX DEPENDENT!! Implementation on other machines is below.
  193.     *
  194.     * Translation: Insert BITS bits from the argument starting at
  195.     * offset bits from the beginning of buf.
  196.     */
  197.    0;    /* Work around for pcc -O bug with asm and if stmt */
  198.    asm( "insv    4(ap),r11,r10,(r9)" );
  199. #else
  200.    /* byte/bit numbering on the VAX is simulated by the following code */
  201.    /* Get to the first byte. */
  202.    bp += (r_off >> 3);
  203.    r_off &= 7;
  204.    /* Since code is always >= 8 bits, only     */
  205.    /* need to mask the first hunk on the left. */
  206.    *bp = (*bp & rmask[r_off]) | (code << r_off);
  207.    bp++;
  208.    code >>= (r_off = 8 - r_off);
  209.    if ((bits -= r_off) >= 8) {
  210.       /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
  211.       *bp++ = code;
  212.       code >>= 8;
  213.       bits -= 8;
  214.    }
  215.    /* Last bits. */
  216.    if (bits) *bp = code;
  217. #endif
  218.    if ((offset += c_n_bits)==(c_n_bits << 3)) {
  219.       if (putpiece(outbuf,c_n_bits) != 0) return -1;
  220.    }
  221.    /* If the next entry is going to be too big for  */
  222.    /* the code size, then increase it, if possible. */
  223.    if (c_free_ent > c_maxcode || c_clear_flg > 0) {
  224.       /* Write the whole buffer, because the input side won't  */
  225.       /* discover the size increase until after it has read it */
  226.       if (offset > 0) {
  227.          if (putpiece(outbuf, c_n_bits) != 0) return -1;
  228.       }
  229.       if (c_clear_flg) {
  230.          c_maxcode = MAXCODE(c_n_bits = INIT_BITS);
  231.          c_clear_flg = 0;
  232.       } else {
  233.          c_maxcode = ++c_n_bits == c_maxbits ?
  234.             c_maxmaxcode : MAXCODE(c_n_bits);
  235.       }
  236.    }
  237.    return 0;
  238. }
  239.  
  240. static int cl_block __ARGS__((void)) /* table clear for block compress */
  241. {
  242.    register long int rat;
  243.  
  244.    c_checkpoint = in_count + CHECK_GAP;
  245.  
  246.    if (in_count > 0x007fffffL) { /* shift will overflow */
  247.       if ((rat = bytes_out >> 8) == 0) {/* Don't divide by zero */
  248.          rat = 0x7fffffffL;
  249.       } else {
  250.          rat = in_count / rat;
  251.       }
  252.    } else {
  253.       rat = (in_count << 8) / bytes_out; /* 8 fractional bits */
  254.    }
  255.    if (rat > ratio) {
  256.       ratio = rat;
  257.    } else {
  258.       ratio = 0;
  259.       cl_hash((count_int)hsize);
  260.       c_free_ent = FIRST;
  261.       c_clear_flg = 1;
  262.       if (output(CLEAR) != 0) return -1;
  263.    }
  264.    return 0;
  265. }
  266.  
  267. int lzwalloc(bits)
  268. int bits;
  269. {
  270. #ifdef XENIX_16
  271.    register i, j; long l;
  272. #endif
  273.    if      (c_maxbits > bits)      c_maxbits = bits;
  274.    else if (c_maxbits < INIT_BITS) c_maxbits = INIT_BITS;
  275. #ifdef XENIX_16
  276.    if (codetab[0]) return c_maxbits;
  277.    if      (c_maxbits >= 16) c_hashsize = 69001L;
  278.    else if (c_maxbits >= 15) c_hashsize = 35023L;
  279.    else if (c_maxbits >= 14) c_hashsize = 18013L;
  280.    else if (c_maxbits >= 13) c_hashsize = 9001L;
  281.    else                      c_hashsize = 5003L;
  282.    for (l=c_hashsize, i=0; i<MAXPAGES && l > 0; i++) {
  283.       j = l > PAGESIZE ? PAGESIZE : (int)l;
  284.       codetab[i] = (word_type *)malloc(sizeof(word_type)*j);
  285.       if (!codetab[i]) break;
  286.       htab[i] = (count_int *)malloc(sizeof(**htab) * j);
  287.       if (!htab[i]) {
  288.          free((char*)(codetab[i])); codetab[i]=WNIL; break;
  289.       }
  290.       l -= j;
  291.    }
  292.    c_hashsize -= l;
  293.    if      (c_hashsize >= 69001L) { j = 16; c_hashsize = 69001L; }
  294.    else if (c_hashsize >= 35023L) { j = 15; c_hashsize = 35023L; }
  295.    else if (c_hashsize >= 18013)  { j = 14; c_hashsize = 18013;  }
  296.    else if (c_hashsize >= 9001)   { j = 13; c_hashsize = 9001;   }
  297.    else if (c_hashsize >= 5003)   { j = 12; c_hashsize = 5003;   }
  298.    else return (lzerror = ZNOMEM, -1);
  299.    if (c_maxbits > j) c_maxbits = j;
  300. #else
  301.    if (codetab) return c_maxbits;
  302.    if ((codetab=(word_type *)malloc(sizeof(*codetab)*_HSIZE))==WNIL ||
  303.        (htab   =(count_int *)malloc(sizeof(*htab)   *_HSIZE))==CNIL) {
  304.       return (lzerror = ZNOMEM, -1);
  305.    }
  306. #endif
  307.    c_maxmaxcode = (code_int)1 << c_maxbits;
  308.    return c_maxbits;
  309. }
  310.  
  311. void lzwfree()
  312. {
  313. #ifdef XENIX_16
  314.    register i;
  315.  
  316.    for (i=0; i<MAXPAGES && codetab[i]!=WNIL; i++) {
  317.       free((char*)(codetab[i])); free((char*)(htab[i]));
  318.    }
  319.    codetab[0] = WNIL;
  320. #else
  321.    if (codetab != WNIL) {
  322.       free((char*)codetab); codetab = WNIL;
  323.       if (htab != CNIL) free((char*)htab);
  324.    }
  325. #endif
  326. }
  327.  
  328. /*
  329.  * Algorithm:  use open addressing double hashing (no chaining) on the
  330.  * prefix code / next character combination.  We do a variant of Knuth's
  331.  * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
  332.  * secondary probe.  Here, the modular division first probe is gives way
  333.  * to a faster exclusive-or manipulation.  Also do block compression with
  334.  * an adaptive reset, whereby the code table is cleared when the compression
  335.  * ratio decreases, but after the table fills.    The variable-length output
  336.  * codes are re-sized at this point, and a special CLEAR code is generated
  337.  * for the decompressor.  Late addition:  construct the table according to
  338.  * file size for noticeable speed improvement on small files.  Please direct
  339.  * questions about this implementation to ames!jaw.
  340.  */
  341.  
  342. static int already = 0;
  343. static int hshift;
  344. static unsigned short ent;
  345.  
  346. int lzwcreat(lzw_out, fsize, wishbits)
  347. #ifdef LZFILE
  348.     FILE *lzw_out;
  349. #else
  350.     int (*lzw_out)__ARGS__((int));
  351. #endif
  352. int wishbits;
  353. long fsize;
  354. {
  355.    register long fcode;
  356.  
  357.    if (lzwalloc(wishbits) < 0) return (lzerror = ZNOMEM, -1);
  358.    c_block_compress = BLOCK_MASK;
  359.    c_checkpoint = CHECK_GAP;
  360.  
  361.    lzw_out_port = lzw_out;
  362.    hsize = _HSIZE;
  363.    /* tune hash table size for small files -- ad hoc,      */
  364.    /* but the sizes match earlier #defines, which          */
  365.    /* serve as upper bounds on the number of output codes. */
  366.    if      (fsize < (1<<12)) hsize = 5003;
  367.    else if (fsize < (1<<13)) hsize = 9001;
  368.    else if (fsize < (1<<14)) hsize = 18013;
  369.    else if (fsize < (1<<15)) hsize = 35023L;
  370.    else if (fsize < 47000L)  hsize = 50021L;
  371.    if (hsize > c_HSIZE) hsize = c_HSIZE;
  372.  
  373.    offset = 0;
  374.    c_clear_flg = 0;
  375.    ratio = 0;
  376.    in_count = 1;
  377.    c_checkpoint = CHECK_GAP;
  378.    c_maxcode = MAXCODE(c_n_bits = INIT_BITS);
  379.    c_free_ent = c_block_compress ? FIRST : 256;
  380.  
  381.    hshift = 0;
  382.    for (fcode = (long)hsize; fcode < 65536L; fcode *= 2L) hshift++;
  383.    hshift = 8 - hshift; /* set hash code range bound */
  384.  
  385.    cl_hash((count_int)hsize); /* clear hash table */
  386.  
  387.    already = 0;
  388.  
  389.    return c_maxbits;
  390. }
  391.  
  392. #define GETBYTE() (--len, char_to_byte(*(char_type *)buf++))
  393.  
  394. int lzwwrite(buf, length)
  395. char *buf; unsigned length;
  396. {
  397.    register long fcode;
  398.    register code_int i = 0;
  399.    register int c;
  400.    register code_int disp;
  401.    register unsigned len = length;
  402.  
  403.    if (!already) {
  404.       if (putbyte(LZW_0TH_MAGIC) != 0 || putbyte(LZW_1ST_MAGIC) != 0 ||
  405.           putbyte((char)(c_maxbits | c_block_compress)) != 0) goto error;
  406.       bytes_out = 3; already = 1; ent = GETBYTE();
  407.    }
  408.    while (len > 0) {
  409.       c = GETBYTE(); in_count++;
  410.  
  411.       fcode = ((long)c << c_maxbits) + ent;
  412.       i = ((code_int)c << hshift) ^ ent; /* xor hashing */
  413.       disp = i ? hsize-i : 1; /* secondary hash (after G. Knott) */
  414.       while (htabof(i) >= 0) {
  415.          if (htabof(i) == fcode) {
  416.             ent = codetabof(i); goto next;
  417.          }
  418.          if ((i -= disp) < 0) i += hsize;
  419.       }
  420.       if (output(ent) != 0) goto error;
  421.       ent = c;
  422.       if (to_compare(c_free_ent) < to_compare(c_maxmaxcode)) {
  423.          codetabof(i) = c_free_ent++; /* code -> hashtable */
  424.          htabof(i)    = fcode;
  425.       }
  426.       else if ((count_int)in_count >= c_checkpoint && c_block_compress) {
  427.          if (cl_block() != 0) goto error;
  428.       }
  429. next: ;
  430.    }
  431.    return length - len;
  432. error:
  433.    lzerror = ZWRITE;
  434.    return -1;
  435. }
  436.  
  437. long lzwclose()
  438. {
  439.    /* Put out the final code & write the rest of the buffer. */
  440.    if (output(ent) != 0 || putpiece(outbuf, (offset+7)/8) != 0)
  441.       return (lzerror = ZWRITE, -1L);
  442.    return bytes_out;
  443. }
  444.